"""A new implementation of the PQ"""

from utils import *
import bisect

class MyPQ(Queue):
    """A queue in which the minimum (or maximum) element (as determined by f and order) is returned first. If order is min, the item with minimum f(x) is returned first; if order is max, then it is the item with maximum f(x)."""

    def __init__(self, order=min, f=lambda x: x, d={}):
        self.A=[]
        self.order=order
        self.f=f
        self.myd=d
        #print type(self.myd)
        #print self.myd[2]
        

    def append(self, item):
        bisect.insort(self.A, (self.f(item), item))
    def __len__(self):
        return len(self.A)
    def pop(self):
        if self.order == min:
            todo = []
            val = self.f(self.A[0][1])
            #print "val is", val, "len a is", len(self.A)
            for i in xrange(len(self.A)):
                if self.f(self.A[i][1]) > val:
                    break
                else:
                    #print "here"
                    todo.append(self.A[i])
                #print todo
            m = pow(2, 20)
            if len(todo) == 0:
                #print "Error"
                exit(0)
            temp = todo[0][1]
            ty = type((1,))
            for j in todo:
                if type(j[1].state) != ty:
                    print j[1].state
                    exit(-1)
                assert type(j[1].state) == ty
                if self.myd[j[1].state] < m:
                    m = self.myd[j[1].state]
                    temp = j
            #
            r = temp[1]
            self.A.remove(temp)
            return r
        else:
	        print "Error"
	        exit(1)
            #return self.A.pop()[1]